/**
 * @param {string} s
 * @param {number} power
 * @param {number} modulo
 * @param {number} k
 * @param {number} hashValue
 * @return {string}
 */
 var subStrHash = function(s, power, modulo, k, hashValue) {
  const val = (ch) => ch.charCodeAt(0) - 'a'.charCodeAt(0) + 1
  const pow = (x, y, mod) => {
    let ans = 1n
    while(y) {
        if(y & 1n){
            ans = ans * x % mod
        }
        x = x * x % mod
        y >>= 1n
    }
    return ans
  }
  const hash = (start, p=BigInt(power), m=BigInt(modulo)) => {
    let sum = 0n
    for(let i = start; i<start+k; i++){
      sum += BigInt(val(s[i])) * pow(p, BigInt(i), m)
    }
    return sum
  }
  const hashPre = (beforeHash, start, p=BigInt(power), m=BigInt(modulo)) => {
    let sum = (beforeHash - BigInt(val(s[start-1])))/p  
    sum += BigInt(val(s[start+k-1]))*pow(p, BigInt(k-1), m)
    return sum
  }
  let pre = hash(0)
  if(pre%BigInt(modulo) === BigInt(hashValue)){
    return s.slice(0, k)
  }
  for(let i = 1; i<s.length-k+1; i++){
    let now = hashPre(pre, i)
    pre = now
    if(now%BigInt(modulo) === BigInt(hashValue)){
      return s.slice(i, i+k)
    }
  }
  return ''
};